package com.love.labuladong.sort.mergesort;

/**
 * 493. 翻转对
 */
public class ReversePairs493 {

    public static int reversePairs(int[] nums) {
        return process(nums,0,nums.length - 1);
    }

    /**
     * 定义 ：arr[l...r] : 上返回翻转对的个数
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int process(int[] arr,int l,int r){
        if(l == r){
            return 0;
        }
        int mid = l + ((r - l) >>> 1);
        // 左
        int left = process(arr,l,mid);
        // 右
        int right = process(arr,mid + 1, r);
        // 跨左右
        int marge = marge(arr,l,mid,r);

        return left + right + marge;
    }


    public static int marge(int[] arr,int start,int mid,int end){

        int ans = 0;
        for (int i = start,j = mid + 1; i <= mid ; i++) {
            // 因为 j 是不会回退的，所以把定义初始化定义放在外部的 for 中（看原理图）
            // 注意 相乘,数据溢出问题
            while (j < end && (long)arr[i] > (long) 2 * arr[j]){
                j++;
            }
            // j 多走了一步,j之前的数则为答案
            ans += j - (mid + 1);
        }
        // 左右排序
        int[] temp = new int[end - start + 1];
        int l = start;
        int r = mid + 1;
        int i = 0;
        while (l <= mid && r <= end){
            temp[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
        }
        while (l <= mid){
            temp[i++] = arr[l++];
        }
        while (r <= end){
            temp[i++] = arr[r++];
        }
        for (int t : temp) {
            arr[start++] = t;
        }
        return ans;
    }


}
